package graph.graphtype;

import graph.GraphNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-08 22:38:04
 */

// 无向加权图 邻接链表实现
public class NoDirectWeightGraph {

//    GraphNode start;
//    GraphNode tail;

    public GraphNode[] table;

    // 节点数量和数据
    public NoDirectWeightGraph(int nodeCount, int[] data){
        table = new GraphNode[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            table[i] = new GraphNode();
            table[i].data = data[i];
            table[i].id = i;
        }
    }

    // 边关系数组
    public void generateGraph(int[][] edges){
        for (int i = 0; i < edges.length; i++) {
            GraphNode newGraphNode = new GraphNode();
            newGraphNode.edgeNode = table[edges[i][1]];
            newGraphNode.id = edges[i][1];

            GraphNode tempGraphNode = table[edges[i][0]];
            while (tempGraphNode.next != null){
                tempGraphNode = tempGraphNode.next;
            }
            tempGraphNode.next = newGraphNode;

            table[edges[i][0]].addWeight(edges[i][1], edges[i][2]);
        }
    }

    // 边关系数组,一条边的关系即可
    public void generateGraphBySingle(int[][] edges){
        for (int i = 0; i < edges.length; i++) {
            // src
            GraphNode newGraphNode = new GraphNode();
            newGraphNode.edgeNode = table[edges[i][1]];
            newGraphNode.id = edges[i][1];

            GraphNode tempGraphNode = table[edges[i][0]];
            while (tempGraphNode.next != null){
                tempGraphNode = tempGraphNode.next;
            }
            tempGraphNode.next = newGraphNode;
            table[edges[i][0]].addWeight(edges[i][1], edges[i][2]);

            // dst
            GraphNode newGraphNode2 = new GraphNode();
            newGraphNode2.edgeNode = table[edges[i][1]];
            newGraphNode2.id = edges[i][1];
            GraphNode tempGraphNode2 = table[edges[i][0]];
            while (tempGraphNode2.next != null){
                tempGraphNode2 = tempGraphNode2.next;
            }
            tempGraphNode.next = newGraphNode;
            table[edges[i][1]].addWeight(edges[i][0], edges[i][2]);
        }
    }

    public List<Integer> dfs(int id){

        int[] visited = new int[table.length];
        List<Integer> result = new ArrayList<>();

        GraphNode tempNode = table[id];
        Stack<GraphNode> stack = new Stack<>();

        stack.add(tempNode);

        while (!stack.isEmpty()){
            tempNode = stack.pop();

            if (visited[tempNode.id] == 1) continue;

            visited[tempNode.id] = 1;
            result.add((Integer)tempNode.data);

            if (result.size() == table.length) break;

            tempNode = tempNode.next;
            while(tempNode != null){
                stack.add(tempNode.edgeNode);// 放table[i] 的值
                tempNode = tempNode.next;
            }

        }

        return result;

    }

    public static void main(String[] args) {
//        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
//                {1, 0, 3}, {1, 3, 1}, {2, 0, 5}, {2, 3, 2}, {2, 4, 4}, {3, 1, 1},
//                {3, 2, 2}, {3, 4, 3}, {4, 0, 1}, {4, 2, 4}, {4, 3, 3}};
//        int[] data = new int[]{1, 2, 3, 4, 5};
//        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
//        g.generateGraph(edges);

        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
                {1, 3, 1}, {2, 3, 2}, {2, 4, 4},
                {3, 4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};
        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
        g.generateGraphBySingle(edges);

        System.out.println("dfs = ");
    }


}
